package days45.title35;

class Solution {
    // 二分法查找数据数组中的插入位置，使得数组保持有序
    public int searchInsert(int[] nums, int target) {
        int left = 0; // 起始点
        int right = nums.length - 1; // 终止点

        // 当起始点不大于终止点时，继续循环查找
        while (left <= right) {
            int mid = left + (right - left) / 2; // 计算中间位置，避免使用模运算

            // 如果目标值等于中间位置的元素，则直接返回中间位置索引
            if (nums[mid] == target) {
                return mid;
            }
            // 如果目标值小于中间位置的元素，则在左半部分继续查找
            else if (nums[mid] > target) {
                right = mid - 1; // 更新终止点
            }
            // 如果目标值大于中间位置的元素，则在右半部分继续查找
            else {
                left = mid + 1; // 更新起始点
            }
        }
        // 如果没有找到等于目标值的元素，则插入位置为起始点（即右侧边界）
        return left;
    }
}